package leetcode.code1541;

import leetcode.IDebug;

public class Solution implements IDebug {

	public int minInsertions(String s) {
		int ans = 0;
		char[] chars = s.toCharArray();
		int L = 0;
		int Lr = 0;
		for (int i = 0; i < s.length(); i++) {
			char c = chars[i];
			if (c == '(') {
				if (Lr == 1) {// 有个`()`
					ans += 1;// 补充一个`)`
					Lr = 0;// 消除`()`
					// L不-1，当前L替代。
				} else {
					L += 1;
				}
			} else if (c == ')') {
				if (L == 0) {// 少`(`
					ans += 1;// 补充一个`(`
					L += 1;
				}
				if (Lr == 0) {// 只有`(`
					Lr += 1;// 变成`()`
				} else {// 有个`()`
					Lr = 0;// 消除`())`
					L -= 1;// L减少乐一个
				}
			}
		}
		if (Lr == 1) {// 有个`()`
			ans += 1;
			L -= 1;
		}
		if (L > 0) {// 还有多余的`(`
			ans += L << 1;
		}
		return ans;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
